package com.yayako.main.struc;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;

/**
 * 图
 *
 * @author cyy
 */
public class Digraph {
    /** 节点总数 */
    private int vertexNum;
    /** 节点列表 */
    private List<Vertex> vertexes;

    private int state;

    Digraph(int v) {
        this.vertexNum = v;
        vertexes = new ArrayList<>();
        for (int i = 0; i < v; ++i) {
            vertexes.add(new Vertex(i, new LinkedList<Vertex.Edge>()));
        }
    }

    Digraph() {
        vertexes = new LinkedList<>();
    }

    public int getAndIncrement() {
        return state++;
    }

    boolean ifCanReachFinal(String word) {
        return goForDFA(getVertex(0), word.toCharArray(), 0);
    }

    private boolean goForDFA(Vertex v, char[] word, int i) {
        if (v == null && i < word.length) {
            return false;
        } else if (i > word.length - 1) {
            return v.isFinal();
        }
        for (Vertex.Edge edge : v.getEdges()) {
            if (edge.getVal() == word[i]) {
                return goForDFA(edge.getTo(), word, i + 1);
            }
        }
        return false;
    }

    int getVertexNum() {
        return vertexNum;
    }

    List<Vertex> getVertexes() {
        return vertexes;
    }

    Vertex getVertex(int v) {
        return vertexes.get(v);
    }

    List<Integer> nextVertex(int v, char target) {
        return vertexes.get(v).nextVertex(target);
    }

    void addVertex(List<Integer> nfaStates) {
        vertexes.add(new Vertex(vertexNum++, nfaStates));
    }

    @Override
    public String toString() {
        //        if (vertexes.get(0).getNfaStates() == null) {
        return getStrForNFA();
        //        } else {
        //            return getStrForDFA();
        //        }
    }

    private String getStrForDFA() {
        StringBuilder res = new StringBuilder();
        res.append("\nε-闭包 (smove({0}) = ")
                .append(vertexes.get(0).nfaStates)
                .append("\t")
                .append(vertexes.get(0).val);
        for (Vertex v : vertexes) {
            res.append(v);
        }
        return res.toString();
    }

    private String getStrForNFA() {
        StringBuilder res = new StringBuilder();
        for (Vertex v : vertexes) {
            for (Vertex.Edge edge : v.getEdges()) {
                if (edge.getTo() == null) {
                    continue;
                }
                res.append(edge);
            }
        }
        return res.toString();
    }

    void addEdge(int from, int to, char val) {
        vertexes.get(from).addEdge(to, val);
    }

    void addEdge(int from, int to) {
        vertexes.get(from).addEdge(to);
    }

    public class Vertex {
        /** 状态量 */
        private int val;
        /** nfa状态集 */
        private List<Integer> nfaStates; // for dfa
        /** 状态转移 */
        private LinkedList<Edge> edges;
        /** 是否为终态 */
        private boolean isFinal;

        private int mState;

        Vertex(int val, LinkedList<Edge> edges) {
            this.val = val;
            this.edges = edges;
        }

        public Vertex(int val) {
            this.val = val;
        }

        Vertex(int val, List<Integer> nfaStates) {
            this.val = val;
            this.nfaStates = nfaStates;
            edges = new LinkedList<>();
        }

        public void setmState(int mState) {
            if (this.mState > 0) {
                return;
            }
            this.mState = mState;
        }

        public void setmState() {
            if (this.mState > 0) {
                return;
            }
            this.mState = getAndIncrement();
        }

        boolean isFinal() {
            return isFinal;
        }

        int getVal() {
            return val;
        }

        void setFinal() {
            isFinal = true;
            mState = 1;
            getAndIncrement();
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Vertex)) {
                return false;
            }
            Vertex vertex = (Vertex) o;
            return Objects.equals(val, vertex.val);
            //            return Objects.equals(nextState(), vertex.nextState());
        }

        @Override
        public int hashCode() {
            return Objects.hash(val);
        }

        @Override
        public String toString() {
            StringBuilder res = new StringBuilder();
            Vertex v;
            for (Edge edge : edges) {
                v = edge.getTo();
                res.append("\nε-闭包 (smove(")
                        .append(val)
                        .append(", ")
                        .append(edge.val)
                        .append(")) = ")
                        .append(v.nfaStates)
                        .append("\t\t")
                        .append(v.val);
            }
            return res.toString();
        }

        List<Integer> nextVertex(char target) {
            List<Integer> list = new LinkedList<>();
            for (Edge edge : edges) {
                if (edge.getVal() == target) {
                    list.add(edge.getTo().val);
                }
            }
            return list;
        }

        List<Integer> nextVertex() {
            List<Integer> list = new LinkedList<>();
            for (Edge edge : edges) {
                list.add(edge.getTo().val);
            }
            return list;
        }

        List<Integer> nextState() { // for minimize dfa
            List<Integer> list = new LinkedList<>();
            for (Edge edge : edges) {
                if (edge.getTo() == null) {
                    list.add(-1);
                } else {
                    list.add(edge.getTo().mState);
                }
            }
            return list;
        }

        LinkedList<Edge> getEdges() {
            return edges;
        }

        private void addEdge(int to, char val) {
            if (to == -1) {
                edges.add(new Edge(null, val));
            } else {
                edges.add(new Edge(getVertex(to), val));
            }
        }

        private void addEdge(int to) {
            edges.add(new Edge(getVertex(to)));
        }

        private List<Integer> getNfaStates() {
            return nfaStates;
        }

        public class Edge {
            /** 转移 */
            private Vertex to;
            /** 输入状态 */
            private char val;

            public Edge(Vertex to, char val) {
                this.to = to;
                this.val = val;
            }

            public Edge(Vertex to) {
                this.to = to;
                this.val = 'ε';
            }

            Vertex getTo() {
                return to;
            }

            char getVal() {
                return val;
            }

            @Override
            public String toString() {
                return "\n\tmove(" + Vertex.this.val + ", " + val + ") = " + to.val;
            }
        }
    }
}
